package leetcode_101_120;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class levelOrder_102 {
    /**
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。
     * （即逐层地，从左到右访问所有节点）。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        /**
         * 还是挺简单的，标记好每一层是第几层。对应好是第几个集合即可
         */
        List<List<Integer>>ans=new ArrayList<>();
        dfs(root,1,ans);
        return ans;
    }
    void dfs(TreeNode node,int k,List<List<Integer>>ans) {
        if(node==null)
            return;
        if(k>ans.size()){  //说明此时的第k层的集合不存在
            List<Integer>list=new ArrayList<>();
            list.add(node.val);
            ans.add(list);
        }else {//存在第k层的集合，直接添加元素
            ans.get(k-1).add(node.val);
        }
        dfs(node.left,k+1,ans);
        dfs(node.right,k+1,ans);
    }
}
